The present invention relates to the communication of digital data using a rate 3/4, 4/5 or 6/7 punctured convolutional code. A method and apparatus in accordance with the present invention provides at least a 0.2 dB coding gain over prior art codes.
Error correcting codes are generally classified into block codes and tree codes. A block code maps m discrete-valued symbols into n discrete-valued symbols using a memoryless coder. Because n is greater than m, redundancy (e.g., parity bits) is introduced in the transmission, which is used to provide error detection and/or correction at the decoder.
A tree code is distinguished from a block code by its encoding process which depends on a past history, or memory, of the input symbols. A type of widely used tree code using binary symbols (i.e., bits) is known as a binary convolutional code. The memory of the encoder is characterized by its state, which is represented as a .nu.-bit binary number. For every m input bits, the encoder outputs n bits based on the m input and .nu. state bits, and then transitions to a next state. The code rate for the convolutional coder is defined by R=m/n&lt;1. Typical rates range from 1/4 to 7/8. In real-time, high data rate applications, the state bits .nu. are limited to be less than or equal to six.
One widely-used technique for efficient maximum likelihood (ML) decoding of convolutional codes is the Viterbi algorithm disclosed in A. J. Viterbi and J. K. Omura, Principles of Digital Communications and Coding, New York, N.Y., McGraw-Hill, 1979. It is known that decoding of high-rate R convolutional codes can be simplified by using "punctured" codes, which are obtained by periodically deleting some of the output bits of a lower rate code. It is well known that a rate 1/n code can be punctured to rate m/k and can be easily decoded with simple modifications to a rate 1/n decoder. An example of such a decoder is provided in commonly assigned, copending U.S. patent application Ser. No. 08/054,642 filed on May 5, 1993 for "Apparatus and Method for Communicating Digital Data Using Trellis Coding with Punctured Convolutional Codes," incorporated herein by reference.
In the prior art, it had first been the practice to take the best (i.e., optimal) rate 1/2 codes of .nu.=2, 3, 4, . . . 8 and puncture them to various rate m/k codes, as described in Y. Yasuda, K. Kashiki and Y. Hirata, "High-Rate Punctured Convolutional Codes for Soft Decision Viterbi Decoding," IEEE Transactions on Communications, Vol. COM-32, No. 3, March, 1984, pp. 315-318. In following work, "optimal" rate (n-1)/n codes punctured from general rate 1/2 codes were reported for n=5, 6, 7, 8 and .nu.=2, 4, . . . 6 in K. J. Hole, "New Short Constraint Length Rate (N-1)/N Punctured Convolutional Codes for Soft-Decision Viterbi Decoding," IEEE Transactions on Information Theory, Vol. IT-34, No. 5, September, 1988, pp. 1079-1081. The codes are "optimal" and better than the Yasuda codes only in their free distance, and thus in their asymptotic coding gain at very high signal-to-noise ratios (SNR).
The present invention provides an advantage in coding gain over the prior art for a rate 1/2, sixteen-state code punctured to rates 3/4, 4/5 and 6/7. The present invention utilizes codes which are not optimal in the traditional free-distance sense, but outperforms such "optimal" codes at low SNRs. Environments with relatively low SNRs are found in concatenated coding systems, where an inner convolutional code (e.g., a trellis code) is wrapped by an outer block code (e.g., a Reed-Solomon code). As a result of the power of the cascaded code, the inner convolutional code may operate at a low SNR.
The code provided by the present invention is also a transparent code and, as such, is highly desirable in its ability to handle 180.degree. phase ambiguities. A binary convolutional code (BCC) is said to be transparent if the complement of any codeword is always a codeword. Since BCCs are linear codes, a BCC is transparent if and only if the "all 1's" sequence is a codeword. A transparent code always has a transparent encoder/uncoder. Such an encoder/uncoder has the property that the output of the uncoder for any codeword is the same as the output when the codeword is first inverted before being presented to the uncoder (i.e., a codeword and its complement produce the same output at the uncoder).